package 递归回溯;

public class No60排列序列 {

    /**
     * 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
     * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
     * "123"
     * "132"
     * "213"
     * "231"
     * "312"
     * "321"
     * 给定 n 和 k，返回第 k 个排列。
     *
     * 示例 1：
     * 输入：n = 3, k = 3
     * 输出："213"
     * 示例 2：
     * 输入：n = 4, k = 9
     * 输出："2314"
     * 示例 3：
     * 输入：n = 3, k = 1
     * 输出："123"
     *  
     *
     * 提示：
     * 1 <= n <= 9
     * 1 <= k <= n!
     */

    private int n;
    private int count;
    private int currentCount;
    private int excludeNum;
    private String result;

    public String getPermutation(int n, int k) {

        //先算单独一个数字有多少的序
        int itemCount=k<2?0:1;
        for (int i = 2; i <= n-1; i++) {
            itemCount*=i;
        }
        int no=itemCount==0?0:k/(itemCount);//0:第一个里面 1:第二个里面 2:第三个里面...  正好对应下标
        if(itemCount!=0&&k%itemCount==0){
            no-=1;
        }
        this.n=n;
        this.count=k-itemCount*no;
        this.excludeNum=no+1;
        StringBuilder sb=new StringBuilder();
        sb.append(excludeNum);
        findStr(sb);
        return result;
    }

    private boolean findStr(StringBuilder path){

        if(path.length()==this.n){
            currentCount++;
        }

        if(path.length()==this.n&&currentCount==this.count){
            result=path.toString();
            return true;
        }else if(path.length()==this.n){
            return false;
        }

        for (int i = 1; i <= this.n; i++) {
            if(i==excludeNum||path.indexOf(String.valueOf(i))!=-1){
                continue;
            }
            path.append(i);
            if(findStr(path)){
                return true;
            }
            path.delete(path.length()-1,path.length());//回溯
        }

        return false;
    }

    public static void main(String[] args) {
        No60排列序列 n=new No60排列序列();
        String result = n.getPermutation(1, 1);
        System.out.println(result);
    }

}
